/*
 * @lc app=leetcode.cn id=240 lang=cpp
 *
 * [240] 搜索二维矩阵 II
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    bool searchMatrix(vector<vector<int>> &matrix, int target)
    {
        int row = 0;
        int col = matrix[0].size() - 1;
        {
            int lr = 0, rr = matrix.size() - 1;
            int r;
            while (lr <= rr)
            {
                r = lr + (rr - lr) / 2;
                if (matrix[r][col] == target)
                    return true;
                if (matrix[r][col] < target)
                {
                    lr = r + 1;
                }
                if (matrix[r][col] > target)
                {
                    rr = r - 1;
                }
            }
            row = r;
        }
        {
            while (row < matrix.size() && matrix[row][0] <= target)
            {
                int ll = 0, rl = matrix[row].size() - 1;
                while (ll <= rl)
                {
                    col = ll + (rl - ll) / 2;
                    if (matrix[row][col] == target)
                    {
                        return true;
                    }
                    if (matrix[row][col] < target)
                    {
                        ll = col + 1;
                    }
                    else
                    {
                        rl = col - 1;
                    }
                }
                row++;
            }
        }
        return false;
    }
};

// int main()
// {
//     vector<vector<int>> m = {{-1,3}};
//     Solution().searchMatrix(m, -1);
//     return 0;
// }
// @lc code=end
